package org.ala.linshen.dp;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
 *
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
 * 输出：4
 * 解释：最长递增路径为 [1, 2, 6, 9]。
 * 示例 2：
 *
 *
 * 输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
 * 输出：4
 * 解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
 * 示例 3：
 *
 * 输入：matrix = [[1]]
 * 输出：1
 *
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 200
 * 0 <= matrix[i][j] <= 231 - 1
 *
 * @author ala
 * @date 2024-09-20 15:25
 */
public class Q329 {

    public static void main(String[] args) {
        Q329 q = new Q329();

//        int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
//        int[][] matrix = {{3,4,5},{3,2,6},{2,2,1}};
//        int[][] matrix = {{1}};
        int[][] matrix = {
                {13, 5,13, 9},
                { 5, 0, 2, 9},
                {10,13,11,10},
                { 0, 0,13,13}};

        System.out.println(q.longestIncreasingPath(matrix));
    }


    public int longestIncreasingPath(int[][] matrix) {
//        return V1(matrix);
        return V2(matrix);
    }
    static int[][] POINTS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    /**
     *  1）堆把矩阵每个坐标点升序
     *  2）从最小点开始：
     *      dp[i][j] = max(dp[_i][_j]) + 1
     *      _i, _j 是 (i,j) 上下左右值比自己小的点，如果没有就是0
     *  3）过程中记录最大的dp
     */
    protected int V1(int[][] matrix) {
        int M = matrix.length, N = matrix[0].length;

        PriorityQueue<int[]> heap = new PriorityQueue<>((p1, p2) -> matrix[p1[0]][p1[1]] - matrix[p2[0]][p2[1]]);
        for (int i = 0 ; i < M ; i++) {
            for (int j = 0 ; j < N ; j++) {
                heap.offer(new int[] {i, j});
            }
        }

        int[][] dp = new int[M][N];
        int max = 0;
        while (!heap.isEmpty()) {
            int[] p = heap.poll();
            int i = p[0], j = p[1], v = matrix[i][j];

            int path = 0;
            for (int[] _p : POINTS) {
                int _i = i + _p[0], _j = j + _p[1];
                if (_i < 0 || _i == M || _j < 0 || _j == N) {continue;}
                int _v = matrix[_i][_j];

                if (v > _v) {
                    path = Math.max(dp[_i][_j], path);
                }
            }
            dp[i][j] += path + 1;
            max = Math.max(max, dp[i][j]);
        }
        return max;
    }


    /**
     *  1）用拓补序的搜索过程，把堆优化掉
     */
    protected int V2(int[][] matrix) {
        int M = matrix.length, N = matrix[0].length;
        //  统计每个点的入度，并记录入度为0的点
        int[][] in = new int[M][N];
        List<int[]> roots = new ArrayList<>();
        for (int i = 0 ; i < M ; i++) {
            for (int j = 0 ; j < N ; j++) {
                for (int[] p : POINTS) {
                    int _i = i + p[0], _j = j + p[1];
                    if (_i < 0 || _i == M || _j < 0 || _j == N || matrix[i][j] <= matrix[_i][_j]) {continue;}
                    in[i][j]++;
                }
                if (in[i][j] == 0) {
                    roots.add(new int[] {i, j});
                }
            }
        }

        //  从入度为0的点出发，统计每个点的路径数
        int[][] dp = new int[M][N];
        int mx = 0;
        while (!roots.isEmpty()) {
            List<int[]> nexts = new ArrayList<>();
            for (int[] r : roots) {
                int i = r[0], j = r[1], _mx = 0;
                for (int[] p : POINTS) {
                    int _i = i + p[0], _j = j + p[1];
                    if (_i < 0 || _i == M || _j < 0 || _j == N) {
                        continue;
                    }
                    if (matrix[i][j] < matrix[_i][_j] && --in[_i][_j] == 0) {
                        nexts.add(new int[] {_i, _j});
                    }
                    if (matrix[i][j] > matrix[_i][_j]) {
                        _mx = Math.max(_mx, dp[_i][_j]);
                    }
                }
                dp[i][j] = _mx + 1;
                mx = Math.max(mx, dp[i][j]);
            }
            roots = nexts;
        }
        return mx;
    }
}
